//
// Created by Zxy on 2020/9/6.
//

#ifndef UNIONFIND_UNIONFIND1_H
#define UNIONFIND_UNIONFIND1_H

#include <cassert>

class UnionFind1 {
private:
    int *id;
    int count;
public:
    UnionFind1(int n){
        count = n;
        id = new int[n];
        for(int i = 0; i < n; i++)
            id[i] = i;
    }
    ~UnionFind1(){
        delete [] id;
    }
    int find(int p){
        assert(p >= 0 && p < count);
        return id[p];
    }
    bool isConnected(int p, int q){
        return find(p) == find(q);
    }
    void unionElements(int p, int q){
        int pID = find(p);
        int qID = find(q);
        if(pID == qID) return;
        // 让p指向q，复杂度O(n)
        for(int i = 0; i < count; i++){
            if(id[i] == pID)
                id[i] = qID;
        }
    }
};


#endif //UNIONFIND_UNIONFIND1_H
